#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e4 + 10;
struct node
{
	int d;
	int ans1, ans2;
}S[N];
string s;
int n, m;
bool st[N];
int dis[N];
int main()
{
	int t;
	cin >> t;
	while (t--) {
		memset(S, 0, sizeof(S));
		memset(st, 0, sizeof(st));
		cin >> n >> m;
		cin >> s;
		for (int i = 0; i <= (1 << n); i++) {
			dis[i] = 0x3f3f3f3f;
		}
		bool flag = 0;
		int a = 0;
		for (int i = 0; i < s.size(); i++) {
			a += ((s[s.size() - i - 1] - '0') << i);
		}
		//cout << "a==" << a << endl;
		dis[a] = 0;
		for (int i = 1; i <= m; i++) {
			int d;
			string s1, s2, s3;
			cin >> d >> s1 >> s2;			
			int ans1 = 0, ans2 = 0;
			for (int j = 0; j < s1.size(); j++) {
				ans1 += (s1[s1.size() - j - 1] - '0') << j;
			}
			for (int j = 0; j < s2.size(); j++) {
				ans2 += (s2[s2.size() - j - 1] - '0') << j;
			}
			S[i] = { d,ans1,ans2 };
			//for (int j = 0; j < s1.size(); j++) {
			//	bool f = 0;
			//	if (s1[j] == '1') f = 1;
			//	else {
			//		if (s2[j] == '1') f = 1;
			//	}
			//	if (f)s3 += "1";
			//	else s3 += "0";
			//}
			////cout << "s3==" << s3 << endl;
			//int ans = 0;
			//for (int j = 0; j < s3.size(); j++) {
			//	ans += (s3[s3.size() - j - 1] - '0') << j;
			//}
			//S[i] = { d,ans };
		}
		priority_queue<PII, vector<PII>, greater<PII>>heap;
		heap.push({ 0,a });
		while (heap.size()) {
			PII z = heap.top();
			heap.pop();
			int ver = z.y;
			int distance = z.x;
			if (st[ver])continue;
			st[ver] = 1;
			for (int i = 1; i <= m; i++) {
				int j = (ver & ~S[i].ans1) | S[i].ans2;
				//cout << "i==" << i << endl;
				//cout << "S[i].ans==" << S[i].ans << endl;
				//cout << "j==" << j << endl;
				if (dis[j] > distance + S[i].d) {
					dis[j] = distance + S[i].d;
					heap.push({ dis[j],j });
				}
			}
		}
		//cout << "ans==";
		if (dis[0] == 0x3f3f3f3f)cout << -1 << endl;
		else cout << dis[0] << endl;
	}
	return 0;
}